package program.leetcode.tree;

import program.tree.SegmentTree;

/**
 * 303. 区域和检索 - 数组不可变
 *
 * 给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。
 *
 * 示例：
 *
 * 给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
 *
 * sumRange(0, 2) -> 1
 * sumRange(2, 5) -> -1
 * sumRange(0, 5) -> -3
 *
 * 说明:
 *
 *     1. 你可以假设数组不可变。
 *     2. 会多次调用 sumRange 方法。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/range-sum-query-immutable
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 解决思路: 使用线段树解决.
 */
public class LeetCode_303 {

    private SegmentTree<Integer> tree;

    public LeetCode_303(int[] nums) {
        Integer[] arr = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = nums[i];
        }

        tree = new SegmentTree<>(arr, Integer::sum);
    }

    public int sumRange(int i, int j) {
        if (tree == null) {
            throw new IllegalArgumentException("No exist data in array!");
        }

        return tree.query(i, j);
    }
}
